package com.xyhuo.leetcode.january;

/**
 * 被列覆盖的最多行数
 * https://leetcode.cn/problems/maximum-rows-covered-by-columns/
 *
 * @time 2024/1/4
 */
public class MaximumRows {

//    public static void main(String[] args) {
//        MaximumRows mr = new MaximumRows();
//        int[][] matrix = {{0, 0, 0}, {1, 0, 1}, {0, 1, 1}, {0, 0, 1}};
//        mr.maximumRows(matrix, 2);
//    }

    public int maximumRows(int[][] matrix, int numSelect) {
        this.n = matrix[0].length;
        int[] already = new int[n];
        search(matrix, already, 0, 0, numSelect);
        return ans;
    }

    private int n;

    private int ans = 0;

    private void search(int[][] matrix, int[] already, int index, int step, int numSelect) {
        if (step == numSelect) {
            int calculate = calculate(matrix, already);
            if (calculate > ans) {
                ans = calculate;
            }
            return;
        }
        for (int i = index; i < n; i++) {
            if (already[i] == 0) {
                already[i] = 1;
                search(matrix, already, i + 1, step + 1, numSelect);
                already[i] = 0;
            }
        }
    }

    private int calculate(int[][] matrix, int[] already) {
        int ans = 0;
        for (int i = 0; i < matrix.length; i++) {
            boolean rowAll = true;
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 1 && already[j] == 0) {
                    rowAll = false;
                    break;
                }
            }
            if (rowAll) {
                ans++;
            }
        }
        return ans;
    }
}
